package offerbook;

/**
 * @date 2019/11/10 0010 下午 3:32
 * <p>
 * 链接：https://www.nowcoder.com/questionTerminal/45327ae22b7b413ea21df13ee7d6429c?answerType=1&f=discussion
 * 来源：牛客网
 * <p>
 * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。
 * 模式中的字符'.'表示任意一个字符，
 * 而'*'表示它前面的字符可以出现任意次（包含0次）。
 * 在本题中，匹配是指字符串的所有字符匹配整个模式。
 * 例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配
 *
 *
    解这题需要把题意仔细研究清楚，反正我试了好多次才明白的。
    首先，考虑特殊情况：
        1>两个字符串都为空，返回true
        2>当第一个字符串不空，而第二个字符串空了，返回false（因为这样，就无法
        匹配成功了,而如果第一个字符串空了，第二个字符串非空，还是可能匹配成
        功的，比如第二个字符串是“a*a*a*a*”,由于‘*’之前的元素可以出现0次，
        所以有可能匹配成功）

    之后就开始匹配第一个字符，这里有两种可能：匹配成功或匹配失败。但考虑到pattern
    下一个字符可能是‘*’， 这里我们分两种情况讨论：pattern下一个字符为‘*’或不为‘*’：
        1>pattern下一个字符不为‘*’(包括'.'或正常字符)：这种情况比较简单，直接匹配当前字符。如果
        匹配成功，继续匹配下一个；如果匹配失败，直接返回false。注意这里的
        “匹配成功”，除了两个字符相同的情况外，还有一种情况，就是pattern的
        当前字符为‘.’,同时str的当前字符不为‘\0’。
        2>pattern下一个字符为‘*’时，稍微复杂一些，因为‘*’可以代表0个或多个。
        这里把这些情况都考虑到：
            a>当‘*’匹配0个字符时，str当前字符不变，pattern当前字符后移两位，
            跳过这个‘*’符号；
            b>当‘*’匹配1个或多个时，str当前字符移向下一个，pattern当前字符
            不变。（这里匹配1个或多个可以看成一种情况，因为：当匹配一个时，
            由于str移到了下一个字符，而pattern字符不变，就回到了上边的情况a；
            当匹配多于一个字符时，相当于从str的下一个字符继续开始匹配）
            之后再写代码就很简单了。


    方式2：用自带的正则表达
 */


public class Code53_RegularMatch {

    /**
     * 利用系统自带的正则，笔试使用该方法
     */
    public boolean match2(char[] str, char[] pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        String s = new String(str);
        String reg = "^" + new String(pattern) + "$";
        return s.matches(reg);
    }

    public boolean match(char[] str, char[] pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        return matchStr(str, 0, pattern, 0);
    }

    private boolean matchStr(char[] str, int i, char[] pattern, int j) {
        //都匹配完了，或者二者都是空串
        if (j >= pattern.length) {
            // i < str.length ,pattern已经匹配完了但是字符串没有匹配完
            return i >= str.length;
        }

        // 有可能 i = str.length 但是 j < pattern.length

        //如果匹配串的 下一个位置是 * ，要做两种处理
        if (j + 1 < pattern.length && pattern[j + 1] == '*') {
            //当 str[i] == pattern[j] || pattern[j] == '.' ,可以匹配0个或1个或多个
            if (i < str.length && (str[i] == pattern[j] || pattern[j] == '.')) {
                return
                        //匹配多个
                        matchStr(str, i + 1, pattern, j) ||
                        //匹配1个
                        matchStr(str, i + 1, pattern, j + 2) ||
                        //匹配0个，如b   b*b，虽然b = b,但是也可以忽略,如果不加第三个分支 ，那么这个会返回false
                        //事实上b*b这种写法不合适，牛客OJ需要加上匹配0个分支，leetcode可以去掉下面这个分支
                        matchStr(str, i, pattern, j + 2);
            } else {
                //否则肯定是匹配0个,如ab   c*ab*, a！=c  或者 i已经到头，如ab  abc*d*e*
                return matchStr(str, i, pattern, j + 2);
            }

            //pattern下一个位置不是 * 或者j == pattern.length -1
        } else if (i < str.length && (str[i] == pattern[j] || pattern[j] == '.')) {
            //如果二者一样或者是 匹配任意字符
            return matchStr(str, i + 1, pattern, j + 1);

        } else {
            //否则匹配不上
            return false;
        }
    }

    public static void main(String[] args) {
        Code53_RegularMatch expression = new Code53_RegularMatch();

        System.out.println(expression.match("b".toCharArray(), "b*b".toCharArray()));
        System.out.println("1".matches("^.*$"));

        System.out.println(expression.match2("1".toCharArray(), ".*".toCharArray()));
    }
}
